Binary tree maximum path sum

Time: O(N); Space: O(H); hard

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: root = {TreeNode} [1,2,3]

  1
 / \
2   3

Output: 6

Example 2:

Input: root = {TreeNode} [-10,9,20,null,null,15,7]

 -10
 / \
9  20
  /  \
 15   7

Output: 42

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H), H is height of BinaryTree
    """
    maxSum = float('-inf')

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxPathSumRecu(root)
        return self.maxSum

    def maxPathSumRecu(self, root):
        if root is None:
            return 0

        left = max(0, self.maxPathSumRecu(root.left))
        right = max(0, self.maxPathSumRecu(root.right))

        self.maxSum = max(self.maxSum, root.val + left + right)

        return root.val + max(left, right)

[3]:

s = Solution1()

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
assert s.maxPathSum(root) == 6

root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
assert s.maxPathSum(root) == 42